package com.datastructure.test.exchangepocketmoney;

import java.util.*;
import java.util.stream.Collectors;

public class ExchangePocketMoney {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
        ExchangePocketMoney exchangePocketMoney = new ExchangePocketMoney();
        int[] data = {5,2,3};
        int minMoney = exchangePocketMoney.minMoney1(data, 20);
        System.out.println(minMoney);
    }

    public int minMoney (int[] arr, int aim) {
        // write code here
        if(arr==null||arr.length==0){
            return -1;
        }
        if(aim==0){
            return 0;
        }
        int[] temp = new int[arr.length];

        Deque<Integer> deque = new ArrayDeque<>();
        getResultSet(arr,deque,aim);
        List<ArrayList<Integer>> collect = res.stream().sorted(Comparator.comparingInt(ArrayList::size)).collect(Collectors.toList());
        return collect.get(0).size();
    }

    public int minMoney1 (int[] arr, int aim) {
        // write code here
        int Max = aim + 1;//定一个全局最大值
        int []dp = new int[aim + 1];//dp[i]的含义是目标值为i的时候最少钱币数是多少。
        Arrays.fill(dp,Max);//把dp数组全部定为最大值
        dp[0] = 0;//总金额为0的时候所需钱币数一定是0
        for(int i = 1;i <= aim;i ++){// 遍历目标值
            for(int j = 0;j < arr.length;j ++){// 遍历钱币
                if(arr[j] <= i){//如果当前的钱币比目标值小就可以兑换
                    dp[i] = Math.min(dp[i],dp[i-arr[j]] + 1);
                }
            }
        }
        return dp[aim] > aim ? -1 : dp[aim];
    }

    public void getResultSet(int[] arr, Deque<Integer> deque,int target){
        if(target<0){
            return;
        }
        if(target==0){
            res.add(new ArrayList<>(deque));
        }
        for (int j : arr) {
            deque.add(j);
            getResultSet(arr, deque, target - j);
            deque.removeLast();
        }
    }
}
